package kmp;

public class Test1 {

    public  int volientMatch(String s,String p) {
        int length = s.length();
        int length1 = p.length();
        int i = 0;
        int j = 0;
        while (i < length && j < length1) {
            if (s.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
            if (j == length1) {
                return i - j;
            }
        }
          return  -1;
    }




        public static int KMP(String Str,String Sub,int pos){
            if (Str == null || Sub == null){
                return -1;
            }
            if (pos >= Str.length() || pos < 0){
                return -1;
            }
            int i = pos;
            int j = 0;
            int[] next = new int[Sub.length()];

            getNext(next,Sub);

            while(i < Str.length() && j < Sub.length()){
                if (j == -1 || Str.charAt(i) == Sub.charAt(j)){
                    i++;
                    j++;
                }else {
                    j = next[j];
                }
            }

            if (j >= Sub.length()){
                return i-j;
            }else {
                return -1;
            }

        }


        public static void getNext(int[] next,String sub){
            next[0] = -1;
            next[1] = 0;

            int i = 2;
            int k = 0;

            //由于我们设定好了next数组前两位的值
            //所以我们使用我们上面所讲到的逻辑就可以很好的完成我们的填充
            while(i < next.length){
                if (k ==- 1 || sub.charAt(k) == sub.charAt(i-1)){
                    next[i] = k+1;
                    i++;
                    k++;
                }else {
                    k = next[k];
                }
            }
        }



    public static void main(String[] args) {
        Test1 test1 = new Test1();
        System.out.println(test1.volientMatch("BBCABCDABABCDABDABDE", "ABCDABD"));
        System.out.println(Test1.KMP("BBCABCDABABCDABDABDE", "ABCDABD", 0));
    }
}
